#include "BTREE.h"

void preOrder(BTNode* root)
{
    if(root==NULL)
    {
        return ;
    }
    printf("%c ",root->data);
    preOrder(root->left);
    preOrder(root->right);
}

void inOrder(BTNode* root)
{
    if(!root)
    {
        return ;
    }
    inOrder(root->left);
    printf("%c ",root->data);
    inOrder(root->right);
}


void postOrder(BTNode* root)
{
    if(!root)
    {
        return ;
    }
    postOrder(root->left);
    postOrder(root->right);
    printf("%c ",root->data);
}


int treesize(BTNode * root)
{
    if(!root)
    {
        return 0;
    }
    return 1+treesize(root->left)+treesize(root->right);
}

int treeheight(BTNode *root)
{
    if(!root)
    {
        return 0;
    }
    int left = treeheight(root->left);
    int right =  treeheight(root->right);
    return  left>right?left+1:right+1;
}

int treelevel(BTNode*root ,int k)
{
    assert(k>0);
    if(root==NULL)
    {
        return 0;
    }
    if(k==1)
    {
        return 1;
    }
    return treelevel(root->left,k-1)+treelevel(root->right,k-1);

}

void BinaryTreeLevelOrder(BTNode* root)//层序遍历，队列
{
    assert(root);
    typedef struct node{
        struct node* next;
        BTNode* data;
    }mynode;
    mynode* head = (mynode*)malloc(sizeof(mynode));
    head->data = root;
    mynode* tail = head;
    tail->next = NULL;
    do{
        printf("%d ",head->data->data);
        if(head->data->left)
        {
            tail->next = (mynode*)malloc(sizeof(mynode));
            tail->next->data = head->data->left;
            tail = tail->next;
            tail->next = NULL;
        }
        if(head->data->right)
        {
            tail->next = (mynode*)malloc(sizeof(mynode));
            tail->next->data = head->data->right;
            tail = tail->next;
            tail->next = NULL;
        }
        mynode* new = head->next;
        free(head);
        head = new;
    }while(head);
    return ;
}

int root_complete(BTNode* root)
{
    if(root->left==NULL && root->left)
    {
        return 0;
    }
    return 1;
}

int BinaryTreeComplete(BTNode* root)
{
    if(root==NULL)
    {
        return 1;
    }
    if(root->left==NULL && root->right)
    {
        return 0;
    }
    if(root->right==NULL && root->left)
    {
        if(root->left->left || root->left->right)
        {
            return 0;
        }
    }
    return BinaryTreeComplete(root->left)&&BinaryTreeComplete(root->right);
}

int BinaryTreeLevelOrder_judge(BTNode * root)//层序遍历判断是否为完全二叉树
{
    assert(root);
    int flag = 0;
    typedef struct node{
        struct node* next;
        BTNode *data;
    }mynode;
    mynode* head = (mynode*)malloc(sizeof(mynode));
    head->data = root;
    mynode* tail = head;
    tail->next=NULL;
    do{
        if(head->data->left)
        {
            if(flag>0)
            {
                return 0;
            }
            tail->next = (mynode*)malloc(sizeof(mynode));
            tail->next->data = head->data->left;
            tail = tail->next;
            tail->next = NULL;
        }
        else
        {
            flag++;
        }
        if(head->data->right)
        {
            if(flag>0)
            {
                return 0;
            }
            tail->next = (mynode*)malloc(sizeof(mynode));
            tail->next->data = head->data->right;
            tail = tail->next;
            tail->next = NULL;
        }
        else
        {
            flag++;
        }
        mynode* new = head->next;
        free(head);
        head = new;
    }while(head);
    return 1;
}


BTNode* BinaryTreeFind(BTNode* root, BTDataType x)//遍历二叉树
{
    if(root==NULL)
    {
        return NULL;
    }
    if(root->data==x)
    {
        return root;
    }
    BTNode*left   = BinaryTreeFind(root->left,x);
    BTNode*right = BinaryTreeFind(root->right,x);
    if(left)
    {
        return left;
    }
    if(right)
    {
        return right;
    }
    return NULL;
}

int BinaryTreeLeafSize(BTNode* root)
{
    if(!root)
    {
        return 0;
    }
    if(root->left==NULL && root->right==NULL)
    {
        return 1;
    }
    return BinaryTreeLeafSize(root->left)+BinaryTreeLeafSize(root->right);
}

BTNode* Buy_treenode(const BTDataType* a)
{
    BTNode* root = (BTNode*)malloc(sizeof(BTNode));
    if(root==NULL)
    {
        perror("malloc fail");
        return NULL;
    }
    root->left = root->right = NULL;
    return root;
}


// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(const BTDataType* a, int n, int* pi)
{
    if(n<=*pi)
    {
        return NULL;
    }
    if(a[*pi]=='#')
    {
        (*pi)++;
        return NULL;
    }
    BTNode* root = Buy_treenode(a);
    root->data = a[(*pi)++];
    root-> left = BinaryTreeCreate(a,n,pi);
    root->right = BinaryTreeCreate(a,n,pi);
    return root;
}

void destory_tree(BTNode* root)
{
    if(root==NULL)
    {
        return ;
    }
    destory_tree(root->left);
    destory_tree(root->right);
    root=NULL;
    return ;
}
int main()
{
    const char* s = "ABD##E#H##CF##G##";
    int len = strlen(s);
    int *arr = (int*)malloc(sizeof(int)*len);
    if(!arr)
    {
        perror("malloc dail");
        return 0;
    }
    int returntreesize = 0;
    for(int i=0;i<len;i++)
    {
        arr[i] = s[i];
    }
    BTNode* p = BinaryTreeCreate(arr,len,&returntreesize);
    preOrder(p);
    printf("\n");
    inOrder(p); 
    printf("\n");
    postOrder(p);
    printf("\n");
    printf("the treeleafsize is %d.",BinaryTreeLeafSize(p));
    printf("\n");
    printf("the treesize is %d\n",treesize(p));
    printf("the k level' rootsnum is %d\n",treelevel(p,3));
    preOrder(BinaryTreeFind(p,'C'));
    printf("\n");
    destory_tree(p);
    free(arr);
    system("pause");
    return 0;
}